package leetcode;

/**
 * 98. 验证二叉搜索树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [2,1,3]
 * 输出：true
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 */
public class IsValidBST {

    public boolean isValidBST(TreeNode root) {
            return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    /**
     * 中序遍历 递归
     *
     * @param node
     * @param lower
     * @param upper
     * @return
     */
    public boolean valid(TreeNode node, long lower, long upper) {
       if (node == null){
           return true;
       }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }

        return valid(node.left, lower, node.val) && valid(node.right, node.val, upper);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }
}
